int partition(double a[], int l, int r, int dir) {
	int i, j;
	double t, pivot;
	pivot = a[l];
	i = l; j = r+1;

	while(1)
	{
		do ++i; while( a[i]*dir <= pivot*dir && i <= r );
		do --j; while( a[j]*dir > pivot*dir );
		if( i >= j ) break;
		t = a[i]; a[i] = a[j]; a[j] = t;
	}
	t = a[l]; a[l] = a[j]; a[j] = t;
	return j;
}

// from the smallest to the largest
void quickSort(double a[], int l, int r, int dir)
{
	int j;

	if( l < r )
	{
		j = partition(a, l, r, dir);
		quickSort(a, l, j-1, dir);
		quickSort(a, j+1, r, dir);
	}
}

int partitionIdx(double a[], int idx[], int l, int r, int dir) {
	int i, j, t;
	double ta, pivot;
	pivot = a[l];
	i = l; j = r+1;

	while(1)
	{
		do ++i; while( a[i]*dir <= pivot*dir && i <= r );
		do --j; while( a[j]*dir > pivot*dir );
		if( i >= j ) break;
		ta = a[i]; a[i] = a[j]; a[j] = ta;
		t = idx[i]; idx[i] = idx[j]; idx[j] = t;
	}
	ta = a[l]; a[l] = a[j]; a[j] = ta;
	t = idx[l]; idx[l] = idx[j]; idx[j] = t;
	return j;
}

void quickIdxSort(double a[], int idx[], int l, int r, int dir)
{
	int j;
	if( l < r )
	{
		j = partitionIdx(a, idx, l, r, dir);
		quickIdxSort(a, idx, l, j-1, dir);
		quickIdxSort(a, idx, j+1, r, dir);
	}
}
